import numpy as np
import sys
import matplotlib
import matplotlib.pyplot as plt
from matplotlib import animation
sys.setrecursionlimit(100000)

r = list()
max_grp_num=list()
secend_grp_num=list()
for i in range (1,100):
    rate=i/100
    r.append(rate)
    def Matrix(matrix,rate):
        num = int(matrix.size * rate)#根据0的比率来得到 0的个数
        new_matrix = np.zeros(matrix.size)#生成与原来模板相同的矩阵，全为1
        new_matrix[:num] = 1 #将一部分换为0
        np.random.shuffle(new_matrix)#将0和1的顺序打乱
        re_array = new_matrix.reshape(matrix.shape)#重新定义矩阵的维度，与模板相同
        return re_array


#得到一个全1矩阵，按照rate的比率生成新矩阵
    mat = np.ones(22500)
    mat2 = mat.reshape(150,150) #原矩阵
    new_mat = Matrix(mat2,rate)
    print("when rate=",rate)
    #print(new_mat)# 新矩阵
    print("\n")
    print(new_mat[0][0])


    num=0
    for m in range(0,150):
        for n in range(0,150):
            a=new_mat[m][n]
            if (a==1):
                num=num+1
            if (a==0):
                num=num

    print("num=",num)

    rows = len(new_mat)
    cols = len(new_mat[0])

    label_table = []
    for i in range(rows):
        col = cols*[0]
        label_table.append(col)

    def show(table):
        rows = len(new_mat)
        cols = len(new_mat[0])
        for i in range(rows):
            for j in range(cols):
                print(table[i][j], end=" ")
            print()

    def dfs(i, j, mask):
        if i<0 or i>=rows or j<0 or j>=cols or label_table[i][j]!=0 or new_mat[i][j]!=1:
            return 0
        label_table[i][j] = mask
        ret = 1
        ret+=dfs(i, j-1, mask)
        ret+=dfs(i, j+1, mask)
        ret+=dfs(i-1, j, mask)
        ret+=dfs(i+1, j, mask)
        return ret

    res = {}
    mask = 1
    for i in range(rows):
        for j in range(cols):
            if new_mat[i][j] == 1 and label_table[i][j] == 0:
                ret = dfs(i, j, mask)
                res[mask] = ret
                mask += 1


    sorted_res = [(k, res[k]) for k in sorted(res, key=res.get, reverse=True)]
    if (len(sorted_res)>1):
        max_grp = sorted_res[0][0]
        max_num = sorted_res[0][1]
        max_grp_num.append(max_num)
        print("max group num: %d belong to max group:%d" % (sorted_res[0][1], max_grp))
        # print(sorted_res)
        secend_grp = sorted_res[1][1]
        secend_grp_num.append(secend_grp)
        print("second group num:%d\n" % sorted_res[1][1])
    if (len(sorted_res)<=1):
        max_num = sorted_res[0][1]
        max_grp = sorted_res[0][0]
        print("max group num: %d belong to max group:%d" % (sorted_res[0][1], max_grp))
        max_grp_num.append(max_num)
        secend_grp_num.append(0)
    print(sorted_res)

plt.title('max_second')  # 折线图标题
plt.rcParams['font.sans-serif'] = ['SimHei']  # 显示汉字
plt.xlabel('rate')  # x轴标题
plt.ylabel('group')  # y轴标题
plt.plot(r,max_grp_num , marker='o', markersize=3)  # 绘制折线图，添加数据点，设置点的大小
plt.plot(r, secend_grp_num, marker='o', markersize=3)
plt.legend(['max_group', 'second_group'])
plt.show()


